/**
 * @file 8Queen.cpp
 * @author Jacob Liu
 * @brief An N-Queen Solver
 * @version 0.1
 * @date 2021-03-18
 *
 * @copyright Copyright (c) Jacob Liu 2021
 *
 */
#include <bits/stdc++.h>
using namespace std;

int N; // the grid is N*N. Preferrably no more than 10.
const int MAXN = 15; // the maximum preferred value of N, above which the program cannot enumerate within a reasonable amount of time.

bool isColOcc[MAXN+1]; // If bit k in this array is 1, the k-th column of the grid is occupied.
bool isPriDiagOcc[2*MAXN+1]; // If bit k in this array is 1, the k-th Primary Diagonal is occupied.
bool isSecDiagOcc[2*MAXN+1]; // If bit k in this array is 1, the k-th Secondary Diagonal is occupied.
unsigned long long countSolutions = 0; // unsigned long long is the largest type of integer universally available in C++

/**
 * @brief The Main Solver for the N-Queen Problem. Finds answers using depth-first-search (DFS).
 * Uses isColOcc[], isPriDiagOcc[], isSecDiagOcc[].
 * @param level: the current level/row in the depth-first-search.
 */
void dfsNQueen(int level) {
    // void here means that this function has no return value.
    if (level == N) { // If we have reached the final level, simply return/stop.
        countSolutions++; // In C++, x++ and ++x is equivalent to "x+=1" in Python.
        return ;
    }
    for (int i = 0; i < N; i++) {
        /*
          In C++, for loops make much more sense.
          the for loop has structure:
          for (A;B;C){
              Do something...
          }
          This is equivalent to:
          A;
          while (B) {
              Do something...
              C;
          }
          common constructs:
          for (int i = 0; i < N; i++){ } iterates i from 0 to N-1 (inclusive).
          for (int i = 1; i <= N; i++){} iterates i from 1 to N (inclusive).
         */
        // This for loop enumerates through all possible positions for the piece on the level-th row.
        if (isColOcc[i] || isPriDiagOcc[level-i+N] || isSecDiagOcc[level+i]) {
            // In C++, "||" means "or"
            // If one of the following occurs, this is not a valid position and we skip to the next position.
            // the column test is trivial
            // On a primary diagonal, the differences of the x and y coordinates is constant.
            // Similarly, on a secondary diagonal, the sums of the x and y coordinates is constant.
            continue;
        }
        // this is a valid position if the code reaches here.
        // change the state of the board.
        isColOcc[i] = true;
        isPriDiagOcc[level-i+N] = true;
        isSecDiagOcc[level+i] = true;
        // move on to the next layer
        dfsNQueen(level+1);
        // restore the state
        isColOcc[i] = false;
        isPriDiagOcc[level-i+N] = false;
        isSecDiagOcc[level+i] = false;
    }
}

int main() {
    memset(isColOcc, 0, sizeof(isColOcc)); // Set all bits to 0 in isColOcc[]
    memset(isPriDiagOcc, 0, sizeof(isPriDiagOcc)); // Set all bits to 0 in isColOcc[]
    memset(isSecDiagOcc, 0, sizeof(isSecDiagOcc)); // Set all bits to 0 in isColOcc[]
    cin >> N; // Input N;
    assert(N <= MAXN && N > 3);
    // "&&" in C++ means "and"
    // assert is a C++ keyword that causes Runtime Error if the expression in brackets is false.
    dfsNQueen(0);
    cout << countSolutions << endl;
    return 0;
}
